package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * @Date 2023/3/19 11:02
 */
public class Num160_GetIntersection {
    /**
     * 结论：思想：ListA+ListB+common = ListB+ListA+Common
     * 条件:如果没有common,当两者个链表都走向null的时候，表示没有相交部分
     */
    /*public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        //使用两个引用listA和listB,同时开始遍历。
        // 如果listA走完了，就走listB.listB也是一样，先走自身，走完了再走listA。
        // 如果两者有相交位置，一定在在相交位置相遇；否则当两者都走完还没相遇，俺就是没有相交节点。
        while (l1 != l2){
            l1 = (l1 == null? headB : l1.next);
            l2 = (l2 == null? headA : l2.next);
        }
        return l1;
    }*/
    /**
     * 单链表的相交，并不是两个链表内的值相等就叫相交，而是两个链表实实在在相交了，也就是说，在某个点相交后，两个链表后面部分就变成一条链子了，
     * 并且，相交后的链表就不可能再分开了，因为，单链表只有一个next指针，如果再分叉，就有两个next指针了，就不符合单链表特性了。
     */

    /**
     * 双指针
     * 注意：求两个链表交点节点的指针。这里要注意，交点不是数值相等，而是指针相等。
     * 通用解法：目前curA指向链表A的头结点，curB指向链表B的头结点。我们求出两个链表的长度，并求出两个链表长度的差值，
     * 然后让curA移动到，和curB 末尾对齐的位置。--------------疑问？这里一定能保证是尾部相交吗？如果是中间相交后面不相交怎么办？还能尾部对齐吗？
     * 此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，
     * 如果遇到curA == curB，则找到交点。否则循环退出返回空指针。*
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //(1)求出两个链表的长度
        ListNode curA = headA;
        ListNode curB = headB;
        int lengthA = 0,lengthB = 0;
        while (curA!=null){
            lengthA++;
            curA = curA.next;
        }
        while (curB!=null){
            lengthB++;
            curB = curB.next;
        }
        //(2)注意这里：让curA一直是那个最长的链表:求出两者的差值，初始化指针curA,curB从头结点开始
        curA = headA;
        curB = headB;
        if(lengthB>lengthA){
            //1. swap (lenA, lenB);
            int tmpLen = lengthA;
            lengthA = lengthB;
            lengthB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //让curA一直走到和curB尾部对齐的地方
        int gap = lengthA-lengthB;
        for (int i = 0; i < gap; i++) {
            curA = curA.next;
        }
        //(3)遍历两个链表，看指针是否相等
        while (curA != null){
            if(curA == curB){
                return curA;
            }else{
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}
